package com.lry.basic.algorithm.tree;


import java.util.*;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/7/1
 */
public class BiTree<T> {
    //根据层序序列建树,返回根节点
    //A,B,C,D,NIL,E,F
    public Node<T> buildTree(T[] datas){
        if(datas==null||datas.length<=0)return null;
        Node root = null;
        Node[] nodes = new Node[datas.length];
        for(int i=0;i<datas.length;i++){
            nodes[i] = new Node(datas[i]);
            if(datas[i]==null){
                nodes[i] = null;
            }
        }
        for(int i=0;i<datas.length;i++){
            Node tmp = nodes[i];
            if(tmp==null)continue;
            if(i==0)root = tmp;
            if(2*i+1<datas.length){
                tmp.left = nodes[2*i+1];
            }else{
                tmp.left = null;
            }
            if(2*i+2<datas.length){
                tmp.right = nodes[2*i+2];
            }else{
                tmp.right = null;
            }
        }
        return root;
    }

    /**
     * 前中序重构二叉树
     * @param preOrder
     * @param inOrder
     * @return
     */
    public Node<T>buildTree(T[]preOrder,T[]inOrder){
        if(null==preOrder||preOrder.length==0||null==inOrder||inOrder.length==0)
            return null;
        return coreBuild(preOrder,0,preOrder.length-1,
                          inOrder,0,inOrder.length-1);
    }
    public Node<T>coreBuild(T[]preOrder,int preStart,int preEnd,
                            T[]inOrder,int inStart,int inEnd){
        Node root = new Node(preOrder[preStart]);
        //叶子节点
        if(preStart==preEnd&&inStart==inEnd)
            return root;
        //找到根节点在中序的下标
        int index=0;
        for(;index<inOrder.length;index++){
            if(inOrder[index]==preOrder[preStart]){
                break;
            }
        }
        //左子树长度
        int leftLen = index - inStart;
        //右子树长度
        int rightLen = inEnd - index;

        if(leftLen>0){
            root.left = coreBuild(preOrder,preStart+1,preStart+leftLen,
                                    inOrder,inStart,index-1);
        }
        if(rightLen>0){
            root.right = coreBuild(preOrder,preStart+leftLen+1,preEnd,
                                    inOrder,index+1,inEnd);
        }
        return root;
    }


    public Node<T>buildTreeByPostAndIn(T[]postOrder,T[]inOrder){
        if(null==postOrder||postOrder.length==0||null==inOrder||inOrder.length==0)
            return null;
        return coreBuildByPostAndIn(postOrder,0,postOrder.length-1,
                inOrder,0,inOrder.length-1);
    }

    public Node<T>coreBuildByPostAndIn(T[]postOrder,int postStart,int postEnd,
                            T[]inOrder,int inStart,int inEnd){
        Node root = new Node(postOrder[postEnd]);
        //叶子节点
        if(postStart==postEnd&&inStart==inEnd)
            return root;
        //找到根节点在中序的下标
        int index=0;
        for(;index<inOrder.length;index++){
            if(inOrder[index]==postOrder[postEnd]){
                break;
            }
        }
        //左子树长度
        int leftLen = index - inStart;
        //右子树长度
        int rightLen = inEnd - index;

        if(leftLen>0){
            root.left = coreBuildByPostAndIn(postOrder,postStart,postStart+leftLen-1,
                    inOrder,inStart,index-1);
        }
        if(rightLen>0){
            root.right = coreBuildByPostAndIn(postOrder,postStart+leftLen,postEnd-1,
                    inOrder,index+1,inEnd);
        }
        return root;
    }



    public void preOrder(Node root){
        if(root!=null){
            System.out.print(root.data+" ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }
    //一直往左边走，走到null。转右边，转完右边继续一直往左边走
    public void preOrderV2(Node root){
        LinkedList<Node> stack = new LinkedList();
        while(!stack.isEmpty()||root!=null){
            //一直往左边走
            while(root!=null){
                System.out.print(root.data+" ");
                stack.push(root);
                root = root.left;
            }
            //跳出上面的while循环意味着往左边走到null，此时需要出栈走一次右边
            if(!stack.isEmpty()){
                root = stack.pop();
                root = root.right;
            }
        }
    }

    public List<Object> preorderTraversal(Node root) {
        List<Object> res = new ArrayList<>();
        LinkedList<Node> stack = new LinkedList();
        while(!stack.isEmpty()||root!=null){
            while(root!=null){
                res.add(root.data);
                stack.push(root);
                root = root.left;
            }
            if(!stack.isEmpty()){
                root = stack.pop();
                root = root.right;
            }
        }
        return res;
    }

    public void preOrderV3(Node root,int length){
        int top=-1;
        Node[] nodes = new Node[length];
        while(root!=null||top!=-1){
            while(root!=null){
                System.out.print(root.data+" ");
                nodes[++top] = root;
                root = root.left;
            }
            if(top!=-1){
                root = nodes[top--];
                root = root.right;
            }
        }
    }
    //非递归前序，中序，后序，层序，深度（不重复遍历），二叉树重建，二叉树镜像。。。
    public void inOrder(Node root){
        if(root!=null){
            inOrder(root.left);
            System.out.print(root.data+" ");
            inOrder(root.right);
        }
    }
    public void inOrderV2(Node root,int length){
        int top=-1;
        Node[] nodes = new Node[length];
        while(top!=-1||root!=null){
            while(root!=null){
                nodes[++top] = root;
                root = root.left;
            }
            if(top!=-1){
                root = nodes[top--];
                System.out.print(root.data+" ");
                root = root.right;
            }
        }
    }
    public List<Node> inOrderV3(Node root){
        List<Node> list = new ArrayList<>();
        LinkedList<Node> stack = new LinkedList();
        while(!stack.isEmpty()||root!=null){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            if(!stack.isEmpty()){
                root = stack.pop();
                list.add(root);
                root = root.right;
            }
        }
        return list;
    }
    public Object inOrderV4(Node root,int k){
        int i=1;
        LinkedList<Node> stack = new LinkedList();
        while(!stack.isEmpty()||root!=null){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            if(!stack.isEmpty()){
                root = stack.pop();
                if(i++==k)return root.data;
                root = root.right;
            }
        }
        return null;
    }
    public void postOrder(Node root){
        if(root!=null){
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.data+" ");
        }
    }
    //根右左 等价于后序遍历的逆序
    public void test(Node root,int length){
        int top=-1;
        Node[] nodes = new Node[length];
        while(top!=-1||root!=null){
            while(root!=null){
                System.out.print(root.data+" ");
                nodes[++top] = root;
                root = root.right;
            }
            if(top!=-1){
                root = nodes[top--];
                root = root.left;
            }
        }
    }

    public void levelOrder(Node root,int length){
        if(root==null||length<=0)return;
        //队列
        Node[] nodes = new Node[length];
        int takeIndex=0,putIndex=0;
        nodes[putIndex] = root;
        putIndex = (++putIndex==length)?0:putIndex;
        while(takeIndex!=putIndex){
            root = nodes[takeIndex];
            System.out.print(root.data+" ");
            nodes[takeIndex] = null;
            takeIndex = (++takeIndex==length)?0:takeIndex;
            if(root.left!=null){
                nodes[putIndex] = root.left;
                putIndex = (++putIndex==length)?0:putIndex;
            }
            if(root.right!=null){
                nodes[putIndex] = root.right;
                putIndex = (++putIndex==length)?0:putIndex;
            }
        }
    }
    public List<List<Node>>levelOrder(Node root){
        List<List<Node>> res = new ArrayList<>();
        if(root==null)return res;
        Queue<Node> queue = new LinkedList();
        queue.add(root);
        while(!queue.isEmpty()){
            List<Node>list = new ArrayList<>();
            int size = queue.size();
            for(int i=0;i<size;i++){
                root = queue.poll();
                list.add(root);
                if(root.left!=null){
                    queue.add(root.left);
                }
                if(root.right!=null){
                    queue.add(root.right);
                }
            }
            res.add(list);
        }
        return res;
    }
    //锯齿形遍历
//    给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
//    例如：
//    给定二叉树 [3,9,20,null,null,15,7],
//            3
//            / \
//            9  20
//            /  \
//            15   7
//    返回锯齿形层次遍历如下：
//            [
//            [3],
//            [20,9],
//            [15,7]
//            ]
    public List<List<Node>>zigzagLevelOrder(Node root){
        List<List<Node>> res = new ArrayList<>();
        if(root==null)return res;
        boolean flag = true;
        Queue<Node> queue = new LinkedList();
        queue.add(root);
        while(!queue.isEmpty()){
            List<Node>list = new ArrayList<>();
            int size = queue.size();
            for(int i=0;i<size;i++){
                root = queue.poll();
                if(flag){//尾部添加
                    list.add(root);
                }else{//首部添加
                    list.add(0,root);
                }

                 if(root.left!=null){
                     queue.add(root.left);
                 }
                 if(root.right!=null){
                     queue.add(root.right);
                 }
            }
            flag = !flag;
            res.add(list);
        }
        return res;
    }

    public int depth(Node root){
        if(root==null)return 0;
        return Math.max(depth(root.left)+1,depth(root.right)+1);
    }
    public boolean isSame(Node root1,Node root2){
        if(root1!=null&&root2==null)return false;
        if(root1==null&&root2!=null)return false;
        if(root1==null&&root2==null)return true;

        if(root1!=null&&root2!=null)
        if(root1.data!=root2.data)
            return false;
        else {
            //&&是关键
           return  isSame(root1.left,root2.left)&&isSame(root1.right,root2.right);
        }
        return false;
    }
    //镜像二叉树
    public boolean isSymmetric(Node root) {
        return isMirror(root,root);
    }
    public boolean isMirror(Node t1,Node t2){
        if(t1==null&&t2==null)return true;
        if(t1==null||t2==null)return false;
        return t1.data==t2.data&&isMirror(t1.left,t2.right)&&isMirror(t1.right,t2.left);
    }
    //翻转二叉树
    public Node invertTree(Node root){
        Node res = root;
        Stack<Node> stack = new Stack();
        while(root!=null||!stack.isEmpty()){
            while(root!=null){
                //翻转
                Node tmp = root.right;
                root.right = root.left;
                root.left = tmp;

                stack.push(root);
                root = root.left;
            }
            if(!stack.isEmpty()){
                root = stack.pop();
                root = root.right;
            }
        }
        return res;
    }

    //min null不参与比较
    public int minDepth(Node root) {
        if(root==null)return 0;

        if(root.left==null){
            return minDepth(root.right)+1;
        }

        if(root.right==null){
            return minDepth(root.left)+1;
        }
        return 1+Math.min(minDepth(root.right),minDepth(root.left));
    }


    public Node inorderSuccessor(Node root, Node p) {
        //找p右孩子的最左节点
        if(p.right!=null){
            Node right = p.right;
            while(right.left!=null){
                right = right.left;
            }
            return right;
        }
        //找p的后继
        else{
            return next(root,p);
        }
    }

    private Node next(Node root, Node p){
        LinkedList<Node> stack = new LinkedList();
        boolean f = false;
        while(root!=null||!stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }

            if(!stack.isEmpty()){
                root = stack.pop();
                if(f){
                    return root;
                }
                if(root==p){
                    f = true;
                }
                root = root.right;
            }
        }
        return null;
    }

    public int maxDepth(Node root){
        if(root==null)return 0;
        else return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }

    //给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
    List<Integer> list  = new ArrayList<>();
    List<List<Integer>>resList = new ArrayList<>();
    public List<List<Integer>> pathSum(Node root, int sum) {
        if(root==null) return resList;
        dfs(root,0,sum);
        return resList;
    }


    public  void dfs(Node root,int tmp,int sum){
        list.add((int)root.data);
        tmp+=(int)root.data;

        if(root.left==null&&root.right==null){
            if(tmp==sum){
                List<Integer>temp = new ArrayList<>();
                temp.addAll(list);
                resList.add(temp);
                return;
            }
        }
        if(root.left!=null){
            dfs(root.left,tmp,sum);
            list.remove(list.size() - 1);
        }
        if(root.right!=null){
            dfs(root.right,tmp,sum);
            list.remove(list.size() - 1);
        }
    }




    private Node n1,n2;
    private Node par;

    public void recoverTree(Node root) {
        inorder(root);
        int tmp = (int) n1.data;
        n1.data = n2.data;
        n2.data = tmp;
    }

    public void inorder(Node node){
        if(null==node){
            return;
        }

        inorder(node.left);

        if(par!=null&& (int)par.data > (int)node.data){
            if(n1==null)
                n1 = par;
            n2 = node;
        }
        par = node;
        inorder(node.right);
    }


    public List<Integer> rightSideView(Node root) {

        List<Integer> list = new ArrayList();
        Node tmp = null;

        Queue<Node> queue = new LinkedList();
        queue.add(root);

        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0;i<size;i++){
                Node node = queue.poll();

                tmp = node;
                if(null!=node.left){
                    queue.add(node.left);
                }

                if(null!=node.right){
                    queue.add(node.right);
                }
            }

            if(tmp!=null){
                list.add((Integer) tmp.data);
            }
        }
        return list;
    }

    public Node lowestCommonAncestor(Node root, Node p, Node q) {
        // LCA 问题
        if (root == null) {
            return root;
        }
        if (root == p || root == q) {
            return root;
        }
        Node left = lowestCommonAncestor(root.left, p, q);
        Node right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            //
            return root;
        } else if (left != null) {
            return left;
        } else if (right != null) {
            return right;
        }
        return null;
    }

    private java.util.Map<String,Integer> memo = new HashMap();
    private List<Node> result = new ArrayList();

    public List<Node> findDuplicateSubtrees(Node root) {
        return result;
    }

    public String dfs(Node node){
        if(null==node){
            return "#";
        }

        String s = node.data+",";
        s = s + dfs(node.left)+",";
        s = s + dfs(node.right);

        int present = 0;
        if((present=memo.getOrDefault(s,0))==1){
            result.add(node);
        }
        memo.put(s,present+1);

        return s;
    }

    List<Node> list1 = new ArrayList();

    public void flatten(Node root) {
        dfs1(root);
        root.left = null;
        root.right = null;
        list1.remove(0);

        Node cur = root;
        for(int i=0;i<list1.size();++i){
            cur.right = list1.get(i);
            cur = cur.right;
        }
    }

    private void dfs1(Node root){
        if(null==root){
            return;
        }
        list1.add(root);
        dfs1(root.left);
        dfs1(root.right);
    }

    public static void main(String[] args) {
//        BiTree<Character> tree = new BiTree<>();
//        int length=6;
//        Character[] datas = {'A','B','C','D','E','F'};
//        Node root = tree.buildTree(datas);
//
//        System.out.println("preOrderV1:");
//        tree.preOrder(root);
//        System.out.println("\npreOrderV2:");
//        tree.preOrderV2(root);
//        System.out.println("\npreOrderV3:");
//        tree.preOrderV3(root,length);
//
//        System.out.println("\ninOrderV1:");
//        tree.inOrder(root);
//        System.out.println("\ninOrderV2:");
//        tree.inOrderV2(root,length);
//        System.out.println("\ninOrderV4:");
//        System.out.println(tree.inOrderV4(root, 2));
//
//        System.out.println("\npostOrder:");
//        tree.postOrder(root);
//        System.out.println("\ntest:");
//        tree.test(root,length);
//
//        System.out.println("\nlevelOrder:");
//        tree.levelOrder(root,length);
//        List<List<Node>> res =  tree.levelOrder(root);
//        System.out.println();
//        for(int i =0;i<res.size();i++){
//            List<Node> list = res.get(i);
//            for(int j=0;j<list.size();j++){
//                System.out.print(list.get(j).data+" ");
//            }
//            System.out.println();
//        }
//
//        res =  tree.zigzagLevelOrder(root);
//        System.out.println("zigzagLevelOrder");
//        for(int i =0;i<res.size();i++){
//            List<Node> list = res.get(i);
//            for(int j=0;j<list.size();j++){
//                System.out.print(list.get(j).data+" ");
//            }
//            System.out.println();
//        }
//
//        System.out.println("\nthe depth of tree:");
//        System.out.println(tree.depth(root));

//        BiTree<Character> tree = new BiTree<>();
//        Node root1 = tree.buildTree(new Character[]{'A',null,'C'});
//        Node root2 = tree.buildTree(new Character[]{'A'});
//        System.out.println(tree.isSame(root1, root2));

//        BiTree<Integer> tree = new BiTree<>();
//        Node root = tree.buildTree(new Integer[]{1,2,2,3,4,4,3});
//        System.out.println(tree.isSymmetric(root));
//        Node root1 = tree.buildTree(new Integer[]{1,2,2,3,4});
//        System.out.println(tree.isSymmetric(root1));
//        Node root2 = tree.invertTree(root1);
//        tree.preOrder(root2);
//        Node root3 = tree.buildTree(new Integer[]{1,2,3,4,null,null,5});
//        System.out.println("\nmaxDepth:"+tree.maxDepth(root3));
//        System.out.println("minDepth:"+tree.minDepth(root3));
//
//        Node root4 = tree.buildTree(new Integer[]{1,2,4,3,5},new Integer[]{4,2,1,3,5});
//        tree.preOrder(root4);
//        tree.inOrder(root4);
//        tree.postOrder(root4);
//        System.out.println();
//        Node root5 = tree.buildTreeByPostAndIn(new Integer[]{4,2,5,3,1},new Integer[]{4,2,1,3,5});
//        tree.preOrder(root5);
//        tree.inOrder(root5);
//        tree.postOrder(root5);

//        BiTree<Integer> tree = new BiTree<>();
//        Node root = tree.buildTree(new Integer[]{5,4,8,11,null,13,4,7,2,null,null,null,null,5,1});
//        System.out.println(tree.minDepth(root));
//        tree.pathSum(root,22);

//        BiTree<Integer> tree = new BiTree<>();
//        Node root = tree.buildTree(new Integer[]{3,5,1,6,2,0,8,null,null,7,4});
//        tree.lowestCommonAncestor(root,root.left.right.left,root.right.right);

        BiTree<Integer> tree = new BiTree<>();
        Node root = tree.buildTree(new Integer[]{1,2,2,4,null,4,5});
        tree.flatten(root);

    }
    static class Node<T>{
        Node left;
        Node right;
        T data;
        Node(T data){
            this.data = data;
        }
    }
}
